/**
 * 面试题53-1：数字在排序数组中出现的次数
 */
public class Offer_53_I {
    /**
     * 方法二：二分查找
     * <p>
     * 「第一个 <b>大于等于</b> target 的数字的下标」记作 leftIndex 和 
     * 「第一个 <b>大于</b> target 的数字的下标减1」记作 rightIndex
     * <p>
     * 时间复杂度：O(logn)
     * <p>
     * 空间复杂度：O(1)
     */
    public int search(int[] nums, int target) {
        int leftIndex = binarySearch(nums, target, true);
        int rightIndex = binarySearch(nums, target, false) - 1;
        // target 可能不存在数组中，因此需要校验
        if (leftIndex <= rightIndex && rightIndex < nums.length 
                && nums[leftIndex] == target && nums[rightIndex] == target) {
            return rightIndex - leftIndex + 1;
        }
        return 0;
    }

    /**
     * 在 nums 数组中二分查找 target 的位置
     * 
     * 如果 lower 为 true，则查找第一个「大于等于」 target 的下标，
     * 
     * 否则查找第一个「大于」 target 的下标
     */
    private int binarySearch(int[] nums, int target, boolean lower) {
        int ans = nums.length;
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    /**
     * 方法一：线性扫描
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     */
    public int search1(int[] nums, int target) {
        int ans = 0;
        for (int num : nums) {
            if (num == target) {
                ans++;
            }
        }
        return ans;
    }
}
